【题解】 [HNOI2015]亚瑟王 概率DP loj2112 | Qiuly's blog!

【题解】 [HNOI2015]亚瑟王 概率DP loj2112

Posted on | Edited on | In | Comments:

发现 $loj$ 真的好用……比 $luogu$ 不知道清爽到哪里去了，更何况 $loj$ 的题目也更多，而且提供数据和代码，更加开放。估计以后都会在 $loj$ 上多逛逛。( $bzoj$ 是真的丑，除非是做 $bzoj$ 的原创题不然我不会上 $bzoj$ 的) 。

顺便贴一下题目传送门：$loj$的传送门就戳我啦(～￣▽￣)～

概率 $\texttt{DP}$ ，设 $f_{i,j}$ 表示打了前 $i$ 张牌，还有 $j$ 轮没有打出牌的概率。我们枚举第 $i+1$ 张牌，分别讨论一下该牌打出与不打出的情况即可。

第一种情况：$j$ 轮中都没有打出第 $i+1$ 张牌，由于一轮中不打出第 $i+1$ 张牌的概率为 $1-p_i$ ，那么 $j$ 轮都不打出该牌的概率显然为 $(1-p_i)^j$ 。转移方程显然：

因为 $f_{i+1,j}$ 可能从多方向转移过来，所以是 $+=$ 。

第二种情况：$j$ 轮中至少有一轮打出了第 $i+1$ 张牌，概率显然为 $1-(1-p_i)^j$ ，转移也就很显然了：

如果我们打出了第 $i+1$ 张牌，那么肯定是要计算贡献的，这个时候直接用这个概率算贡献就好了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=3e2+2;
int T,n,r,d[N];
double f[N][N],p[N],pw[N][N];

int main() {
    scanf("%d",&T);
    while(T--) {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&r);
        for(int i=1;i<=n;++i) scanf("%lf%d",&p[i],&d[i]);
        for(int i=1;i<=n;++i) {
            pw[i][0]=1;
            for(int j=1;j<=r;++j) pw[i][j]=pw[i][j-1]*(1-p[i]);
        }
        f[0][r]=1;
        double ans=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<=r;++j) {
                f[i+1][j]+=f[i][j]*pw[i+1][j];
                if(j) {
                    double calc=f[i][j]*(1-pw[i+1][j]);
                    f[i+1][j-1]+=calc,ans+=calc*d[i+1];
                }
            }
        printf("%.10f\n",ans);
    }
    return 0;
}

本文标题:【题解】 [HNOI2015]亚瑟王 概率DP loj2112

文章作者:Qiuly

发布时间:2019年04月28日 - 00:00

最后更新:2019年04月29日 - 21:18

原始链接:http://qiulyblog.github.io/2019/04/28/[题解]loj2112/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。